Dr. J's Maths.com
Where the techniques of Maths
are explained in simple terms.

Networks and Graph Theory - Minimum Spanning Trees.
Test Yourself 1.


 

Remember - with minumum spanning trees, we are including all vertices but looking for the minimum sum of the weights on the edges.

Kruskal's algorithm is used when the context allows us to start at any edge.

Prim's algorithm is used when we are given a starting point (vertex).

This page contains questions on:
1. Applying Kruskal's algorithm.
2. Applying Prim's algorithm.
3. Comparing results obtained using both algorithms.

 

Using Kruskal's algorithm. 1. A weighted network diagram is shown at the left.

What is the weight of the minimum spanning tree?
  2.
Answer.Minimum weight is 11.		 A weighted network diagram is shown at the left.

What is the weight of the minimum spanning tree?
  3.
Answer.The minimum length of piping is 180 m and it will cost $9,000.		 In a holiday park consisting of eight cabins, the owner want to connect the electricity to each cabin. As electric cable costs $50 per metre, the owner needs to minimise the length of the connections but must connect all cabins.

What is the shortest path the owner can use to connect all the cabins? What is the total cost of the cable required?
  4. (i) What is the weight of the minimum spanning tree in the network shown below?
(ii) Show the network for that minimum spanning tree.

Answer.The weight of the minimum spanning tree is 37.
  5.
Answer.The minimum length of piping is 34 km along E-D-C-B-A.

The diagram at the left shows 5 locations linked by possible paths to install water pipes. The numbers along the edges are the distances between the locations in kilometres.

Water can be supplied to the system starting any any one of the five locations.

What is the minimum total pipe length required to deliver water to all five locations?
  6. A network of pipes, connected to pumping stations labeled with the letters L to R, is shown in the diagram with the length of each pipe (in kilometres) indicated.

The network is to be reduced in complexity by eliminating several pipes but retaining all the pumping stations.

(i) Determine the minimum spanning tree that will achieve the stated goal.

(ii) What is the minimum length of pipe needed to connect all of the stations.

Answer.The minimum length of piping is 142 kms.
  7. Need a table
  8. A park has five areas (A, B, C, D and E) all connected by pathways.

The following table shows the length of some of those pathways.

  A B C D E
A   600     ?
B 600   ? 500  
C   ?   400  
D   500 400   300
E ?     300  

 

The following network diagram shows the information contained in the table as well as the relevant minimum spanning tree (shown in blue).

(i) Complete the network diagram using the information contained in the table.

Include a possible value for each of the two edges AE and BC (shown in black) which are omitted from the minimum spanning tree.

(ii) Justify, giving two reasons, why AE and BC were not included as part of the minimum spanning tree.
Using Prim's algorithm.

9. Determine the minimum spanning tree and its weight for the following weighted network:

(i) starting with vertex C;

(ii) starting with vertex E.

Answer.Both networks have a total weight of 14.
  10. A nursery has to make deliveries of various garden supplies to four customers in a given locality. The operations manager takes the distances (in metres) between the customers from Google Maps and records them in the following table.
  A B C D
A   650   280
B 650   500 220
C   500   340
D 280 220 340  

(i) What is the shortest distance the delivery truck should travel to deliver to all 4 customers starting with A - which is the customer closest to the depot?

(ii) What is the shortest path to be taken?

Answer.(i) Shortest distance = 1000 m.
(ii) Shortest path is A-D-B-C.
  11. Robyn is helping her father to plan the watering system to be installed in the backyard. The plan is to connect the tap to eight spray points and so they prepare a map of their yard with the required spray points as shown below. They indicate the distance in metres between the points on the edges of their plan.

Because she is a good student in Maths, her father asks Robyn to analyse their map to determine the minimum amount of piping they will need to connect the eight spay points to the tap.

(i) Prepare the plan with which Robyn will be able to show the minimum length of pipes from the tap.

(ii) Calculate the length of piping required for that minimum connection.

Answer.The minimum length of piping is 31 metres.
  12. Check that the weighted network given in Q 4 above gives the same network diagram and the same weight when using Prim's algorithm if J is selected as the starting vertex.
  13.
 

14. Fibre optic cables are to be laid at a rural school which consists of 5 buildings. The consultants have assessed the requirements for all feasible connections and estimated the cost (in hundreds of dollars) for each connection. Connections between some buildings are impractible.

The consultants' cost estimates are summarised in the table below. The missing entries indicate the connections which cannot be considered.

 

(i) Use the table above to complete a weighted network diagram based on the cost to connect the buildings.

(ii) Determine the network path with minimum costs to connect all buildings.

(iii) What is the minimum cost to cable the school?

 
 

15.
  16.
Comparison

17.The diagram below shows a network.

(i) Calculate the minimum spanning tree using Kruskal's algorithm.

(ii) Calculate the minimum spanning tree using Prim's algorithm starting from vertex F.

(iii) Compare your results.

Answer.(i) Using Kruskal, the minimum path has a weight of 39 (see solutions for the path).
(ii) Using Prim, the path is altered slightly and the weight increases to 41.
  18. .